Pattern matching is the application of analytical rules to a block of data to identify a feature of that block of data.
The most common pattern matching problem is the process of finding some or all occurrences of a sequence of elements [Y1 . . . Ym] (target pattern) within a larger sequence of elements [X1 . . . Xn] (source pattern). The elements come from a finite element set—an alphabet set. The set may be the English alphabet, {0,1}, natural numbers, etc. The most popular algorithms for this problem are the Knuth-Morris-Pratt algorithm, the Boyer-Moore algorithm and the Rabin-Karp algorithm.
There are a number of pattern matching tools in the public domain. The most prominent of these are the grep family.
Pattern matching is used for simple text search, searching for data in image data, speech data, video data, audio data, biomedical sequence analysis, etc.
Data compression is mainly used for reducing storage space and to speed up data transmission. Various forms of compression are known. Of particular interest is arithmetic coding compression for which compressed pattern matching has not heretofore been possible.
Arithmetic coding originated in the 1970s and 1980s (see for example U.S. Pat. No. 4,122,440). Arithmetic coding is used in several applications, including Speech and Medical Image compression.
In compressed pattern matching, the pattern matching is performed in the compressed domain. Succinctly put, compressed pattern matching of, for example, text strings can be stated as:                Let ac be a given compression algorithm, let ac(D) be the result of ac compressing data f)        Input: compressed text ac(T) and compressed pattern ac(P)        Output: all or some locations in T where pattern P occurs.        
Amir and Benson (“Efficient Two-dimensional Compressed Matching”, in Proc. Second IEEE Data Compression Conference, pp 279-288, March 1992) showed that complexity of pattern matching is reduced in the compressed domain compared to any conventional method in the uncompressed domain.
However, it has not been considered possible to perform pattern matching on “arithmetic codes” without decompressing that data (“TR-COSC 07/01 Pattern Matching in Compressed Texts and Images”, by Tim Bell et al, Technical Reports, University of Canterbury, available at http://www.cosc.canterbury.ac.nz/research/reports/TechReps/2001/tr—0107.pdf